package com.zlk.algorithm.algorithm.dynamicPlan;

import com.sun.xml.internal.ws.api.model.wsdl.editable.EditableWSDLBoundFault;
import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName MinimumCostForTickets
 * @description:https://leetcode.cn/problems/minimum-cost-for-tickets/
 *
 * @author: slfang
 * @create: 2024-03-27 09:04
 * @Version 1.0
 **/
public class Code02_MinimumCostForTickets {

    // 最低票价
    // 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
    // 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
    // 每一项是一个从 1 到 365 的整数
    // 火车票有 三种不同的销售方式
    // 一张 为期1天 的通行证售价为 costs[0] 美元
    // 一张 为期7天 的通行证售价为 costs[1] 美元
    // 一张 为期30天 的通行证售价为 costs[2] 美元
    // 通行证允许数天无限制的旅行
    // 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
    // 那么我们可以连着旅行 7 天(第2~8天)
    // 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费


    public int mincostTickets(int[] days, int[] costs) {
        int[] durations = new int[]{1,7,30};
        //return minCost(days,costs,durations,0);
//        int[] dp = new int[days.length];
//        for (int i = 0; i < days.length; i++) {
//            dp[i] = Integer.MAX_VALUE;
//        }
//        return minCostCache(days,costs,durations,0,dp);
        return minCostBest(days,costs,durations);
    }

    private int minCost(int[] days, int[] costs, int[] durations,int i) {
        if(i==days.length){
            return 0;
        }

        // 一张 为期1天 的通行证售价为 costs[0] 美元
        // 一张 为期7天 的通行证售价为 costs[1] 美元
        // 一张 为期30天 的通行证售价为 costs[2] 美元

        //  2  20
        //  2  3  5
        int min = Integer.MAX_VALUE;
        for (int k = 0; k < 3; k++) {
            int j = i;
            //只选一次一种的,一种只跑一次cost 不会走多个，因为现在策略就是每次找到一种来试。
            while (j<days.length&&days[j]<durations[k]+days[i]){
               j++;
            }
            min = Math.min(costs[k]+minCost(days,costs,durations,j),min);
        }
        return min;
    }

    private int minCostCache(int[] days, int[] costs, int[] durations,int i,int[] dp) {
        if(i==days.length){
            return 0;
        }
        if(dp[i]!=Integer.MAX_VALUE){
            return dp[i];
        }
        // 一张 为期1天 的通行证售价为 costs[0] 美元
        // 一张 为期7天 的通行证售价为 costs[1] 美元
        // 一张 为期30天 的通行证售价为 costs[2] 美元

        //  2  20
        //  2  3  5
        int min = Integer.MAX_VALUE;
        for (int k = 0; k < 3; k++) {
            int j = i;
            //只选一次一种的,一种只跑一次cost 不会走多个，因为现在策略就是每次找到一种来试。
            while (j<days.length&&days[j]<durations[k]+days[i]){
                j++;
            }
            min = Math.min(costs[k]+minCostCache(days,costs,durations,j,dp),min);
        }
        dp[i] = min;
        return min;
    }

    //从底到顶的 动态规划
    private int minCostBest(int[] days, int[] costs, int[] durations) {
        int[] dp = new int[days.length+1];
        for (int i = 0; i < days.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        dp[days.length] = 0;
        for (int j = days.length; j >=0; j--) {
            //int minJ = Integer.MAX_VALUE;
            for (int k = 0; k < 3; k++) {
                int index = j;
                //只选一次一种的,一种只跑一次cost 不会走多个，因为现在策略就是每次找到一种来试。
                while (index<days.length&&durations[k]+days[j]>days[index]){
                    index++;
                }
                dp[j] = Math.min(costs[k]+dp[index],dp[j]);
            }
        }
        return dp[0];
    }

////////////////////////////////////////////////////////联系//////////////////////////////////////////////////////////////////////////////////////////////////
    // 最低票价
    // 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
    // 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
    // 每一项是一个从 1 到 365 的整数
    // 火车票有 三种不同的销售方式
    // 一张 为期1天 的通行证售价为 costs[0] 美元
    // 一张 为期7天 的通行证售价为 costs[1] 美元
    // 一张 为期30天 的通行证售价为 costs[2] 美元
    // 通行证允许数天无限制的旅行
    // 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
    // 那么我们可以连着旅行 7 天(第2~8天)
    // 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费


    public int mincostTickets2(int[] days, int[] costs) {
        int[] gap = new int[]{1,7,30};
        int[] dp = new int[days.length+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        return f1(0,days,costs,gap);
    }

    private int f1(int i, int[] days, int[] costs,int[] gap) {
        //base case
        if(i==days.length){
            return 0;
        }
        int res = Integer.MAX_VALUE;
        //遍历所有情况
        for (int k = 0; k < costs.length; k++) {
            //找到costs中能包含的所有数组索引，并且找到下一个
            int j = i;
            // while (j<days.length&&days[j]<durations[k]+days[i]){
            while (j<days.length&&days[j]<days[i]+gap[k]){
               j++;
            }
            res = Math.min(res,f1(j,days,costs,gap)+costs[k]);
        }
        return res;
    }

    //记忆化搜索
    // f(i)
    private int f2(int i, int[] days, int[] costs,int[] gap,int[] dp) {
        if(i==days.length){
            return 0;
        }
        if(dp[i]!=Integer.MAX_VALUE){
            return dp[i];
        }
        int res = Integer.MAX_VALUE;
        //遍历所有情况
        for (int k = 0; k < costs.length; k++) {
            //找到costs中能包含的所有数组索引，并且找到下一个
            int j = i;
            // while (j<days.length&&days[j]<durations[k]+days[i]){
            while (j<days.length&&days[j]<days[i]+gap[k]){
                j++;
            }
            res = Math.min(res,f2(j,days,costs,gap,dp)+costs[k]);
        }
        dp[i] = res;
        return res;
    }


    /**
     * 从低到顶的动态规划
     */
    private int f3(int[] days,int[] costs,int[] gap){
        int[] dp = new int[days.length+1];
        for (int i = days.length-1; i>=0; i--) {
            int res = Integer.MAX_VALUE;
            for (int k = 0; k < costs.length; k++) {
                int j = i;
                while (j<days.length&&days[j]<days[i]+gap[k]){
                    j++;
                }
                res = Math.min(res,dp[j]+costs[k]);
            }
            dp[i] = res;
        }
        return dp[0];
    }

    @Test
    public void test(){//
        int[] days = new int[]{1,4,6,7,8,20};
        int[] costs  = new int[]{2,7,15};

        mincostTickets2(days,costs);

    }


}
